/*
https://leetcode.cn/problems/longest-common-subsequence/

*/
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        // 获取两个字符串的长度
        int m = text1.length(), n = text2.length();

        // 创建一个二维动态规划数组 dp，初始化为 0
        // dp[i][j] 表示 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列长度
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        // 遍历 text1 和 text2
        for (int i = 1; i <= m; i++) {
            // 获取 text1 中的第 i 个字符
            char c1 = text1.at(i - 1);

            for (int j = 1; j <= n; j++) {
                // 获取 text2 中的第 j 个字符
                char c2 = text2.at(j - 1);

                // 如果两个字符相等
                if (c1 == c2) {
                    // 更新 dp[i][j] 为 dp[i - 1][j - 1] + 1
                    // 这意味着在公共子序列中增加了一个字符
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 如果两个字符不相等
                    // dp[i][j] 取 dp[i - 1][j] 和 dp[i][j - 1] 中的较大值
                    // 这意味着我们要么忽略 text1 中的字符，要么忽略 text2 中的字符
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // 返回 dp[m][n]，即 text1 和 text2 的最长公共子序列的长度
        return dp[m][n];
    }
};
